﻿
namespace Leetcode.N0322.V1;

public class Solution
{
    public int CoinChange(int[] coins, int amount)
    {
        coins = coins.OrderByDescending(_ => _).ToArray();

        var count = this.CoinChange2(coins, amount, new Dictionary<int, int>());
        return count == int.MaxValue ? -1 : count;
    }

    private int CoinChange2(int[] coins, int amount, IDictionary<int, int> cache)
    {
        if (amount == 0)
        {
            return 0;
        }

        if (amount < 0)
        {
            return -1;
        }

        if (cache.ContainsKey(amount))
        {
            return cache[amount];
        }

        var minCount = int.MaxValue;
        for (int i = 0; i < coins.Length; i++)
        {
            var nextCount = this.CoinChange2(coins, amount - coins[i], cache);
            if (nextCount == -1)
            {
                continue;
            }
            minCount = Math.Min(minCount, nextCount + 1);
        }
        minCount = minCount == int.MaxValue ? -1 : minCount;
        cache.Add(amount, minCount);
        return minCount;
    }

}
